Subscribe to see which companies asked this question

这道题刚开始拿到的时候，没有什么思路，参考了一下网上别人的思路。很多人就说dp算法和BFS算法去解这道题。但是我是个菜鸟啊。我根本就不懂什么是dp算法啊。然后代码也没有啥注释根本就看不懂啊。然后我就自己去研究了一下代码和DP算法。

DP算法说通俗一点 就是大事化小事，然后循环或者递归处理它。具体的思路网上也有讲，都感觉比较复杂而且比较抽象。针对这道题我们的思路就是如果我们传一个不定值得amount，还用同样的数组去组合怎么得到解。我们比较好理解的就是从1开始然后+1，这样迭代上去，都用同一套规则来判断。这个部分算是一个提示，帮助大家好独立思考完成题目。下面具体讲一下每一步的思路和代码。

int com(const void *a, const void *b){return *(int *)a - *(int *)b;}int coinChange(int* coins, int coinsSize, int amount) {int i, j, n = 0;int nVal;//首先申请一个和amount+1一样大的数组Array，表示从0-amount遍历全部情况。int *array = (int*)malloc(sizeof(int)*(amount+1));//这里要给coins从小到大排序一下qsort(coins, coinsSize, sizeof(int), com);//0的情况就是不需要组合  所以可以给Array[0] = 0。array[0] = 0;//后后面的思路就是 遍历全部Array数组, i 就是对应的要通过硬币组合出来的数字,Array[i]对应的就是存要的硬币的最小值。for (i = 1 ; i < amount+1; ++i){//先给每个里面付初始值amount+1,。array[i] = amount+1;//然后对应的遍历所有的coins数组。for (j = 0; j < coinsSize && coins[j]